#include <stdio.h>
#include <stdlib.h>
#define Max 100
#define ElementType int

typedef struct
{
    ElementType arr[Max];
    int len;
}Arr;

void InitArr(Arr *a)
{
    for(int i = 0; i < Max; i++)
    {
        a->arr[i] = 0;
    }
    a->len = 0;
}

void InsertTail(Arr *a,ElementType element)
{
    if(a->len >= Max)
    {
        printf("数组已满!\n");
        return;
    }
    a->arr[a->len++] = element;
}

void InsertHead(Arr *a,ElementType element)
{
    if(a->len >= Max)
    {
        printf("数组已满!\n");
        return;
    }
    for(int i = a->len; i > 0; i--)
    {
        a->arr[i] = a->arr[i-1];
    }
    a->arr[0] = element;
    a->len++;
}

void InsertByIndex(Arr *a,int index,ElementType element)
{
    if(a->len >= Max)
    {
        printf("数组满!\n");
        return;
    }
    if(index < 0 || index > a->len)
    {
        printf("非法插入位置!\n");
        return;
    }
    for(int i = a->len; i > index; i--)
    {
        a->arr[i] = a->arr[i-1];
    }
    a->arr[index] = element;
    a->len++;
}

void RemoveByIndex(Arr *a,int index)
{
    if(index < 0 || index >= a->len)
    {
        printf("非法位置删除!\n");
        return;
    }
    if(a->len == 0)
    {
        printf("数组空!\n");
        return;
    }
    for(int i = index; i < a->len; i++)
    {
        a->arr[i] = a->arr[i + 1];
    }
    a->len--;
}

void RemoveByElement(Arr *a,ElementType element)
{
    if(a->len == 0)
    {
        printf("数组空!\n");
        return;
    }
    for(int i = 0; i < a->len; i++)
    {
        if(a->arr[i] == element)
        {
            RemoveByIndex(a,i);
            i--;
        }
    }
}

void UpdataByIndex(Arr *a,int index,ElementType element)
{
    if(index < 0 || index >= a->len)
    {
        printf("修改位置非法!\n");
        return;
    }
    a->arr[index] = element;
}

void UpdataByElement(Arr *a,ElementType oldValue,ElementType newValue)
{
    for(int i = 0; i < a->len; i++)
    {
        if(a->arr[i] == oldValue)
        {
            a->arr[i] = newValue;
        }
    }
}

ElementType* FindByIndex(Arr *a,int index)
{
    if(index < 0 || index >= a->len)
    {
        printf("寻找位置非法!\n");
        return NULL;
    }
    return &a->arr[index];
}

// int* FindByElement(Arr *a,ElementType element)
// {
//     int *indexArr = (int*)malloc(sizeof(int) * (a->len + 1));
//     if(indexArr == NULL)
//     {
//         printf("malloc error!\n");
//         return NULL;
//     }
//     int count = 0;
//     // for(int i = 0; i < a->len; i++)
//     // {
//     //     if(a->arr[i] == element)
//     //     {
//     //         count++;
//     //         indexArr[count] = i;
//     //     }
//     // }
//     // indexArr[0] = count;

//     for(int i = 0; i < a->len; i++)
//     {
//         if(a->arr[i] == element)
//         {
//             indexArr[i] = i;
//             count++;
//         }
//     }
//     indexArr[count] = -1;
//     return indexArr;
// }

Arr* FindByElement(Arr *a,ElementType element)
{
    Arr *p = (Arr*)malloc(sizeof(Arr));
    if(p == NULL)
        return NULL;
    InitArr(p);
    for(int i = 0; i < a->len; i++)
    {
        if(a->arr[i] == element)
        {
            InsertTail(p,i);
        }
    }
    return p;
}

void FastSort(Arr *a,int start,int end)
{
    if(start >= end)
        return;
    int left = start;
    int right = end;
    int temp = a->arr[left];

    while(left < right)
    {
        while(left < right && a->arr[right] > temp)
        {
            right--;
        }
        if(left < right)
        {
            a->arr[left] = a->arr[right];
            left++;
        }
        while(left < right && a->arr[left] < temp)
        {
            left++;
        }
        if(left < right)
        {
            a->arr[right] = a->arr[left];
            right--;
        }
    }
    a->arr[left] = temp;
    FastSort(a,start,left-1);
    FastSort(a,right+1,end);
}

void Dumplicate(Arr *a)
{
    FastSort(a,0,a->len-1);
    for(int i = 0; i < a->len - 1; i++)
    {
        if(a->arr[i] == a->arr[i + 1])
        {
            RemoveByIndex(a,i);
            i--;
        }
    }
}

Arr* FindInsection(Arr *a1,Arr *a2)
{
    Arr *p = (Arr*)malloc(sizeof(Arr));
    if(p == NULL)
        return NULL;
    InitArr(p);
    for(int i = 0; i < a1->len; i++)
    {
        for(int j = 0; j < a2->len; j++)
        {
            if(a1->arr[i] == a2->arr[j])
            {
                InsertTail(p,a1->arr[i]);
                break;
            }
        }
    }
    Dumplicate(p);
    return p;
}

Arr* FindUnionSet(Arr *a1,Arr *a2)
{
    Arr *p = (Arr*)malloc(sizeof(Arr));
    if(p == NULL)
        return NULL;
    InitArr(p);
    
    for(int i = 0; i < a1->len; i++)
    {
        InsertTail(p,a1->arr[i]);
    }
    for(int i = 0; i < a2->len; i++)
    {
        InsertTail(p,a2->arr[i]);
    }
    Dumplicate(p);
    return p;
}

Arr* Merge(Arr *a1,Arr *a2)
{
    Arr *p = (Arr*)malloc(sizeof(Arr));
    if(p == NULL)
        return NULL;
    InitArr(p);

    int i = 0;
    int j = 0;
    while(i < a1->len && j < a2->len)
    {
        if(a1->arr[i] < a2->arr[j])
        {
            InsertTail(p,a1->arr[i]);
            i++;
        }
        else
        {
            InsertTail(p,a2->arr[j]);
            j++;
        }
    }
    while(i < a1->len)
    {
        InsertTail(p,a1->arr[i]);
        i++;
    }
    while(i < a2->len)
    {
        InsertTail(p,a2->arr[j]);
        j++;
    }
    return p;
}

int BinarySearch(Arr *a,ElementType element)
{
    int left = 0;
    int right = a->len - 1;

    while(left <= right)
    {
        int mid = left + (right - left) / 2;
        if(a->arr[mid] == element)
        {
            return mid;
        }
        if(a->arr[mid] > element)
        {
            right = mid - 1;
        }
        if(a->arr[mid] < element)
        {
            left = mid + 1;
        }
    }
    return -1;
}

void Travel(Arr *a)
{
    printf("len : %d",a->len);
    printf("\n=======================================\n");
    for(int i = 0; i < a->len; i++)
    {
        printf("%d ",a->arr[i]);
    }
    printf("\n=======================================\n");
}
int main()
{
    Arr a1;
    InitArr(&a1);
    for(int i = 2; i <= 11; i++)
    {
        InsertTail(&a1,i);
    }
    Travel(&a1);
    Arr a2;
    InitArr(&a2);
    for(int i = 1; i <= 10; i++)
    {
        InsertTail(&a2,i);
    }
    Travel(&a2);

    Arr *p = Merge(&a1,&a2);
    Travel(p);

    printf("%d\n",BinarySearch(&a1,4));

    
    return 0;
}